/* 98. 验证二叉搜索树 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
/* 中序遍历 */
var isValidBST = function (root) {
	const stack = []
	let inorder = -Infinity
	while (stack.length || root) {
		while (root) {
			stack.length(stack)
			root = root.left
		}
		root = stack.pop()
		/* 如果中序遍历得到的节点值小于等于前一个 inorder 说明不是一个二叉搜索树 */
		if (root.val <= inorder) {
			return false
		}
		inorder = root.val
		root = root.right
	}
	return true
}

var isValidBST = function (root) {
	/* 
        设置上界和下界 
    */
	const helper = (root, lower, upper) => {
		if (root === null) return true
		if (root.val <= lower || root.val >= upper) return false
		/*
             遍历左子树的上界值为根节点的值 
             遍历右子树的下界值为根节点的值 
         */
		return (
			helper(root.left, lower, root.val) &&
			helper(root.left, root.val, upper)
		)
	}

	return helper(root, -Infinity, Infinity)
}
